package com.cqs.leetcode.dp;

import com.google.common.base.Stopwatch;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @author lixqw
 * @date 2020/8/22
 */
public class ContinuousSubarraySum523 {


    static class Solution {
        /**
         * 暴力美学
         *
         * @param nums
         * @param k
         * @return
         */
        public boolean checkSubarraySum(int[] nums, int k) {
            for (int i = 0; i < nums.length - 1; i++) {
                int sum = nums[i];
                for (int j = i + 1; j < nums.length; j++) {
                    sum += nums[j];
                    if (k == 0) {
                        if (sum == 0) return true;
                    } else if (sum % k == 0) return true;
                }
            }
            return false;
        }
    }

    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> sumIndex = new HashMap<>();
        if(k == 1 || k == -1 ) return nums.length > 1;
        int sum = 0;
        sumIndex.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (k == 0 && sum == 0 && i > 0) {
                return true;
            }
            if (k != 0) sum = sum % k;
            Integer idx = sumIndex.getOrDefault(sum, i - 1);
            if (idx != i - 1) {
                return true;
            }
            sumIndex.putIfAbsent(sum, i);
        }
        return false;
    }


    public static void main(String[] args) {
        ContinuousSubarraySum523 sub = new ContinuousSubarraySum523();
        int[] test = new int[10000];
        for (int i = 0; i < test.length; i++) {
            test[i] = 1;
            if (new Random().nextFloat() > 10.8) {
                test[i] = test[i] * -1;
            }
        }
        test = new int[]{-3, 3, 8, 1, 5};
        test = new int[]{0, 0};

//            ArraysUtils.print(test);

        int k = new Random().nextInt(1000000000);
        k = 9;
        k = 0;
        Stopwatch stopwatch = Stopwatch.createStarted();
        boolean b = new Solution().checkSubarraySum(test, k);
        boolean s2 = new ContinuousSubarraySum523().checkSubarraySum(test, k);
        System.out.println(b + "\t" + s2);
        stopwatch.stop();


        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 2);
        map.putIfAbsent(1, 3);
        System.out.println(map.get(1));
        System.out.println(0 % -1);

    }
}
